package com.lhcai.lc.category.matrix;

/**
 * 240. 搜索二维矩阵 II
 *
 * @author liuhuaicai
 * @since 2025-01-04 20:57
 */
public class Lc240 {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] ints : matrix) {
            // 剪枝
            if (ints[ints.length - 1] < target) {
                continue;
            }
            if (ints[0] > target) {
                return false;
            }
            // 搜索
            if (search(ints, target)) {
                return true;
            }
        }
        return false;
    }
    private boolean search(int[] ints, int target) {
        // 二分查找
        int left = 0;
        int right = ints.length - 1;
        while (left <= right) {
            int middle = (left + right) >> 1;
            if (ints[middle] == target) {
                return true;
            } else if (ints[middle] > target) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        return false;
    }
}
